Linux Cubed Series 3: Developer Tools/Linux Cubed Series 3 - Developer Tools.iso/devel/lang/eiffel/smalleif.97/se.t/SmallEiffel/lib_std/array.e

Text File | 1996-05-02 | 6.0 KB | 317 lines

-- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C)
-- Dominique COLNET and Suzanne COLLIN -- [e-mail]
--
class ARRAY[E]
--
-- General purpose arrays.
--

inherit COLLECTION[E];

creation {ANY}
   make

feature {NONE}

   storage: POINTER;
     -- Internal access to storage location.

feature

   capacity: INTEGER;
     -- Internal storage capacity in number of item.

   lower: INTEGER;
     -- Lower index bound.

   upper: INTEGER;
     -- Upper index bound.

feature -- Creation and Modification :

   make(minindex, maxindex: INTEGER) is
     -- Make array with range [minindex .. maxindex].
     -- When maxindex = minindex - 1, the array is empty.
      require
     minindex -1 <= maxindex
      do
     if storage /= Void then
        c_inline_c("free(C->_storage);");
     end;
     lower := minindex;
     upper := maxindex;
     capacity := upper - lower + 1;
     storage := Void;
     if capacity > 0 then
        capacity := capacity + 16;
        c_inline_c("C->_storage=malloc%
               %((size_t)((C->_capacity)*sizeof(*(C->_storage))));");
        clear_all;
     end;
      ensure
     lower = minindex;
     upper = maxindex;
     all_cleared;
      end;

feature -- Modification :

   resize(minindex, maxindex: INTEGER) is
     -- Resize the array. No elements will be lost in the
     -- intersection of [old lower .. old upper] and
     -- [minindex .. maxindex].
     -- New positions are initialized with appropriate
     -- default values.
      require
     minindex <= maxindex
      local
     other: like Current;
     i, up: INTEGER;
      do
     from
        !!other.make(minindex,maxindex);
        i := lower.max(other.lower);
        up := upper.min(other.upper);
     until
        i > up
     loop
        other.put(item(i),i);
        i := i + 1;
     end;
     if storage /= Void then
        c_inline_c("free(C->_storage);");
     end;
     c_inline_c("memcpy(C,_other,sizeof(*C));free(_other);");
      end;

feature -- No modification :

   infix "@", item (index: INTEGER): E is
      do
     check
        storage /= Void;
        capacity >= (upper - lower + 1);
     end;
     c_inline_c("R=(C->_storage)[a1-(C->_lower)];")
      end;

feature -- Modification :

   put(element: E; index: INTEGER) is
     -- Put `element' at position `index'.
      do
     c_inline_c("(C->_storage)[a2-(C->_lower)]=a1;");
      end;

   force(element: E; index: INTEGER) is
     -- Put `element' at position `index'.
     -- Resize array, if `index' is not
     -- inside current bounds.
      do
     if upper < index then
        resize(lower,index);
     elseif index < lower then
        resize(index,upper);
     end;
     put(element,index);
      ensure
     valid_index(index);
     item(index) = element;
      end;

   clear is
     -- Empty the array, discard all items.
      do
     upper := lower - 1;
      ensure
     empty;
      end;

   copy(other: like Current) is
     -- Copy `other' onto Current.
      local
     i: INTEGER;
      do
     upper := lower - 1;
     if capacity = 0 then
        make(other.lower,other.upper);
     else
        resize(other.lower,other.upper);
     end;
     from
        i := lower;
     until
        i > upper
     loop
        put(other.item(i),i);
        i := i + 1;
     end;
      end;

   remove(index: INTEGER) is
     -- Remove one element at position `index'. Followings
     -- elements (after `index') are moved one position left.
      require
     valid_index(index);
      local
     i: INTEGER;
      do
     from
        i := index;
     until
        i + 1 > upper
     loop
        put(item(i + 1),i);
        i := i + 1;
     end;
     upper := upper - 1;
      ensure
     count + 1 = old count;
     upper + 1 = old upper;
      end;

   remove_last is
      require
     not empty;
      do
     upper := upper - 1;
      ensure
     count = 1 + old count;
      end;

   remove_first is
      require
     not empty;
      do
     lower := lower + 1;
      ensure
     count = 1 + old count;
      end;

feature -- Adding Elements :

   add_last(elt: E) is
      do
     if capacity < count + 1 then
        capacity := capacity + 16;
        if capacity = 16 then
           c_inline_c("C->_storage=malloc(16*sizeof(*(C->_storage)));");
        else
           c_inline_c("C->_storage=realloc(C->_storage,%
              %((C->_capacity)*sizeof(*(C->_storage))));");
        end;
     end;
     upper := upper + 1;
     put(elt,upper);
      ensure
     last = elt;
     count = 1 + old count
      end;

   add(elt: E) is
      do
     if not has(elt) then
        add_last(elt);
     end;
      ensure
     has(elt);
     count >= old count;
      end;

   fast_add(elt: E) is
      do
     if not fast_has(elt) then
        add_last(elt);
     end;
      ensure
     fast_has(elt);
     count >= old count;
      end;

   insert(element : E; index: INTEGER) is
     -- Insert `element' after position `index'.
     -- Element at position `upper' will be lost!
      require
     inside_bounds: lower - 1 <= index and then index < upper
     -- Note: Insertion is AFTER `index'!
      do
     if index < upper - 1 then
        move(index+1,upper-1,1);
     end;
     put (element, index + 1);
      end;

   sub_array(low, up: INTEGER): ARRAY[E] is
      require
     valid_index(low);
     valid_index(up);
     low <= up
      local
     i: INTEGER;
      do
     from
        !!Result.make(low,up);
        i := low;
     until
        i > up
     loop
        Result.put(item(i),i);
        i := i + 1;
     end;
      ensure
     Result.lower = low;
     Result.upper = up;
      end;

feature -- Other Features :

   put_first(elt: E) is
     -- Put `elt' at the first free place
     -- or `add_last' it no Void places.
      local
     i: INTEGER;
     null: E;
      do
     from
        i := lower;
     until
        i > upper or else item(i) = null
     loop
        i := i + 1;
     end;
     if i > upper then
        add_last(elt);
     else
        put(elt,i);
     end;
      end;

   take_first: E is
     -- Take the first element non Void or not set to
     -- the default value. Then set the corresponding
     -- place to the default value.
      local
     i: INTEGER;
     null: E;
      do
     from
        i := lower;
     until
        i > upper or else Result /= null
     loop
        Result := item(i);
        i := i + 1;
     end;
     if i <= upper then
        put(null,i-1);
     end;
      ensure
     count = old count;
      end;

invariant

   capacity >= (upper - lower + 1);

end -- ARRAY[E]